package main

import "fmt"

//暴力解法,用时548ms 5%，内存2.3MB 54%
func longestPalindrome(s string) string {
	maxString := ""
	for i := 0; i < len(s); i++ {
		for j := i + 1; j <= len(s); j++ {
			if isPalindrome(s[i:j]) {
				if len(maxString) < len(s[i:j]) {
					maxString = s[i:j]
				}
			}
		}
	}
	return maxString
}
func isPalindrome(s string) bool {
	for i := 0; i < len(s)/2; i++ {
		if s[i] != s[len(s)-i-1] {
			return false
		}
	}
	return true
}

//动态规划88ms 15%, 6.8MB 10%
func longestPalindrome1(s string) string {
	maxString := string(s[0])
	if len(s) == 1 {
		return s
	}
	dp := [][]bool{}
	for i := 0; i < len(s); i++ {
		dp = append(dp, make([]bool, len(s)))
		dp[i][i] = true
	}
	for L := 2; L < len(s)+1; L++ {
		for i := 0; i < len(s); i++ {
			j := L + i - 1
			if j > len(s)-1 {
				break
			}
			if s[i] != s[j] {
				dp[i][j] = false
			} else if j-i < 3 {
				dp[i][j] = true
			} else {
				dp[i][j] = dp[i+1][j-1]
			}
			if dp[i][j] && j-i+1 > len(maxString) {
				maxString = s[i : j+1]
			}
		}
	}
	return maxString
}

//中心扩展算法,0ms 100%,2.3MB 82%
func longestPalindrome2(s string) string {
	start, end := 0, 0
	for i := 0; i < len(s); i++ {
		left1, right1 := expand(s, i, i)
		left2, right2 := expand(s, i, i+1)
		if right1-left1 > end-start {
			start, end = left1, right1
		}
		if right2-left2 > end-start {
			start, end = left2, right2
		}
	}
	return s[start : end+1]
}

func expand(s string, i, j int) (int, int) {
	for ; i >= 0 && j < len(s) && s[i] == s[j]; i, j = i-1, j+1 {
	}
	return i + 1, j - 1
}

func main() {
	s := "dddd"
	fmt.Println(longestPalindrome(s))
	fmt.Println(s[0:1])
	fmt.Println(longestPalindrome1("ac"))
	fmt.Println(longestPalindrome2("adsdsds"))
}
